/**
 * 二叉搜索树
 */

// 创建BinarySearchTree
function BinarySerachTree() {
    // 创建节点构造函数
    function Node(key) {
        this.key = key
        this.left = null
        this.right = null
    }

    // 保存根的属性
    this.root = null
    
    // 向树中插入数据
    BinarySerachTree.prototype.insert = function (key) {
        // 1.根据key创建对应的node
        var newNode = new Node(key)

        // 2.判断根节点是否有值
        if (this.root === null) {
            this.root = newNode
        } else {
            this.insertNode(this.root, newNode)
        }
    }

    // 内部递归插入数据的函数
    BinarySerachTree.prototype.insertNode = function (node, newNode) {
        if (newNode.key < node.key) { // 1.准备向左子树插入数据
            if (node.left === null) { // 1.1.node的左子树上没有内容
                node.left = newNode
            } else { // 1.2.node的左子树上已经有了内容
                this.insertNode(node.left, newNode)
            }
        } else { // 2.准备向右子树插入数据
            if (node.right === null) { // 2.1.node的右子树上没有内容
                node.right = newNode
            } else { // 2.2.node的右子树上有内容
                this.insertNode(node.right, newNode)
            }
        }
    }

    // 遍历方法
    // 1. 先序遍历
    BinarySerachTree.prototype.preOrderTraversal = function (handler) {
        this.preOrderTranversalNode(this.root, handler)
    }
    // 递归树结构
    BinarySerachTree.prototype.preOrderTranversalNode = function (node, handler) {
        if (node != null) {
            handler(node.key)
            // 树左子节点
            this.preOrderTranversalNode(node.left, handler)
            // 树右子节点
            this.preOrderTranversalNode(node.right, handler)
        }
    }

    // 2. 中序遍历
    BinarySerachTree.prototype.midOrderTraversal = function (handler) {
        this.midOrderTranversalNode(this.root, handler)
    }
    BinarySerachTree.prototype.midOrderTranversalNode = function (node, handler) {
        if (node != null) {
            // 树左子节点
            this.midOrderTranversalNode(node.left, handler)
            handler(node.key)
            // 树右子节点
            this.midOrderTranversalNode(node.right, handler)
        }
    }
    
    // 3. 后序遍历
    BinarySerachTree.prototype.afterOrderTraversal = function (handler) {
        this.afterderTranversalNode(this.root, handler)
    }
    BinarySerachTree.prototype.afterderTranversalNode = function (node, handler) {
        if (node != null) {
            // 树左子节点
            this.afterderTranversalNode(node.left, handler)
            // 树右子节点
            this.afterderTranversalNode(node.right, handler)
            handler(node.key)
        }
    }
}

// 测试代码
var bst = new BinarySerachTree()
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)

// 先序遍历
var preResToString = ""
bst.preOrderTraversal(function (key) {
    preResToString += key + " "
})
console.log(preResToString) // 11 7 5 3 6 9 8 10 15 13 12 20 18 25

// 中序遍历
var midResToString = ""
bst.midOrderTraversal(function (key) {
    midResToString += key + " "
})
console.log(midResToString) // 3 5 6 7 8 9 10 11 12 13 15 18 20 25
// 后序遍历
var afterResToString = ""
bst.afterOrderTraversal(function (key) {
    afterResToString += key + " "
})
console.log(afterResToString) // 3 6 5 8 10 9 7 12 13 18 25 20 15 11
